#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/3/7 8:36
# ===========================================
#       题目名称： 35. 搜索插入位置
#       题目地址： https://leetcode.cn/problems/search-insert-position/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================


class Solution:
    def searchInsert(self, nums, target):
        if not nums:
            return 0
        left, right = 0, len(nums) - 1
        while left <= right:
            # 左右开弓
            if nums[left] >= target:
                return left
            if nums[right] <= target:
                return right + 1 if nums[right] < target else right
            # 控制一下边界
            if left + 1 == right:
                return left + 1
            left += 1
            right -= 1


if __name__ == "__main__":
    s = Solution()
    print("nums = [1,3], target = 2 =>", s.searchInsert(nums=[1, 3], target=2))  # 1
    print("nums = [1,3,5,6], target = 5 =>", s.searchInsert(nums=[1, 3, 5, 6], target=5))  # 2
    print("nums = [1,3,5,6], target = 2 =>", s.searchInsert(nums=[1, 3, 5, 6], target=2))  # 1
    print("nums = [1,3,5,6], target = 7 =>", s.searchInsert(nums=[1, 3, 5, 6], target=7))  # 4
